---
id: 594810f028c0303b75339ad6
title: ゼッケンドルフの定理
challengeType: 1
forumTopicId: 302346
dashedName: zeckendorf-number-representation
---

# --description--

Just as numbers can be represented in a positional notation as sums of multiples of the powers of ten (decimal) or two (binary); all the positive integers can be represented as the sum of one or zero times the distinct members of the Fibonacci series. Recall that the first six distinct Fibonacci numbers are: `1, 2, 3, 5, 8, 13`.

10 進数の 11 は、各列がフィボナッチ数列の特定の要素による乗算を表す位取り記数法で `0*13 + 1*8 + 0*5 + 1*3 + 0*2 + 0*1` または `010100` のように記述することもできます。 先頭のゼロを落として、10 進数の 11 が `10100`になるようにします。 フィボナッチ数から 11 を作る方法は 10100 だけではありませんが、 `0*13 + 1*8 + 0*5 + 0*3 + 1*2 + 1*1` または 010011もまた、10 進数の 11 を表しています。 真のゼッケンドルフ表現については、*2 つの連続するフィボナッチ数を使用できない*という追加の制限があり、それが前の一意の解ということにつながります。

# --instructions--

`n` の ゼッケンドルフ表現を生成して返す関数を記述してください。

# --hints--

`zeckendorf` は関数とします。

```js
assert.equal(typeof zeckendorf, 'function');
```

`zeckendorf(0)` は `0` を返す必要があります。

```js
assert.equal(zeckendorf(0), 0);

```

`zeckendorf(1)` は `1` を返す必要があります。

```js
assert.equal(zeckendorf(1), 1);
```

`zeckendorf(2)` は `10` を返す必要があります。

```js
assert.equal(zeckendorf(2), 10);
```

`zeckendorf(3)` は `100` を返す必要があります。

```js
assert.equal(zeckendorf(3), 100);
```

`zeckendorf(4)` は `101` を返す必要があります。

```js
assert.equal(zeckendorf(4), 101);
```

`zeckendorf(5)` は `1000` を返す必要があります。

```js
assert.equal(zeckendorf(5), 1000);
```

`zeckendorf(6)` は `1001` を返す必要があります。

```js
assert.equal(zeckendorf(6), 1001);
```

`zeckendorf(7)` は `1010` を返す必要があります。

```js
assert.equal(zeckendorf(7), 1010);
```

`zeckendorf(8)` は `10000` を返す必要があります。

```js
assert.equal(zeckendorf(8), 10000);
```

`zeckendorf(9)` は `10001` を返す必要があります。

```js
assert.equal(zeckendorf(9), 10001);
```

`zeckendorf(10)` は `10010` を返す必要があります。

```js
assert.equal(zeckendorf(10), 10010);
```

`zeckendorf(11)` は `10100` を返す必要があります。

```js
assert.equal(zeckendorf(11), 10100);
```

`zeckendorf(12)` は `10101` を返す必要があります。

```js
assert.equal(zeckendorf(12), 10101);
```

`zeckendorf(13)` は `100000` を返す必要があります。

```js
assert.equal(zeckendorf(13), 100000);
```

`zeckendorf(14)` は `100001` を返す必要があります。

```js
assert.equal(zeckendorf(14), 100001);
```

`zeckendorf(15)` は `100010` を返す必要があります。

```js
assert.equal(zeckendorf(15), 100010);
```

`zeckendorf(16)` は `100100` を返す必要があります。

```js
assert.equal(zeckendorf(16), 100100);
```

`zeckendorf(17)` は `100101` を返す必要があります。

```js
assert.equal(zeckendorf(17), 100101);
```

`zeckendorf(18)` は `101000` を返す必要があります。

```js
assert.equal(zeckendorf(18), 101000);
```

`zeckendorf(19)` は `101001` を返す必要があります。

```js
assert.equal(zeckendorf(19), 101001);
```

`zeckendorf(20)` は `101010` を返す必要があります。

```js
assert.equal(zeckendorf(20), 101010);
```

# --seed--

## --seed-contents--

```js
function zeckendorf(n) {

}
```

# --solutions--

```js
// zeckendorf :: Int -> Int
function zeckendorf(n) {
  const f = (m, x) => (m < x ? [m, 0] : [m - x, 1]);
  return parseInt((n === 0 ? ([0]) :
    mapAccumL(f, n, reverse(
      tail(fibUntil(n))
    ))[1]).join(''));
}

// fibUntil :: Int -> [Int]
let fibUntil = n => {
  const xs = [];
  until(
      ([a]) => a > n,
      ([a, b]) => (xs.push(a), [b, a + b]), [1, 1]
  );
  return xs;
};

let mapAccumL = (f, acc, xs) => (
  xs.reduce((a, x) => {
    const pair = f(a[0], x);

    return [pair[0], a[1].concat(pair[1])];
  }, [acc, []])
);

let until = (p, f, x) => {
  let v = x;
  while (!p(v)) v = f(v);
  return v;
};

const tail = xs => (
   xs.length ? xs.slice(1) : undefined
);

const reverse = xs => xs.slice(0).reverse();
```
